package gintrie

import "strings"

//RadixNode 前缀树节点
type RadixNode struct {
	//Path 相对路径
	Path string
	//FullPath 完整路径,父节点到当前节点的完整路径拼接
	FullPath string
	//Indices 索引串，将所有子级的首字母拼接而成
	Indices string
	//End 是否有单词以该节点为末尾存在
	End bool
	//Children 子节点数组切片
	Children []*RadixNode
	//PassCnt 统计经过该节点的字符数
	PassCnt int
}

//RadixTree 前缀压缩树
type RadixTree struct {
	Root *RadixNode
}

//NewRadixTree 创建一个前缀树
func NewRadixTree() *RadixTree {
	return &RadixTree{
		Root: &RadixNode{},
	}
}

//Insert 插入一个词
func (t *RadixTree) Insert(word string) {
	// 检查是否已存在word，如果存在，则不执行插入
	if t.Search(word) {
		return
	}

	t.Root.insert(word)
}

//insert 插入树节点
func (t *RadixNode) insert(word string) {
	fullWord := word
	// 如果根节点为空，那么直接插入
	if t.Path == "" && len(t.Children) == 0 {
		t.End = true
		t.Path = word
		t.FullPath = t.Path
		t.PassCnt++
		return
	}

	// 和根节点进行匹配比较
LOOP:
	for {
		i := getCommonPrefixIdx(word, t.Path)
		if i > 0 {
			t.PassCnt++
		}

		// 如果公共前缀长度小于当前节点的相对路径
		// 需要对当前的公共前缀做拆分，把公共的部分变成父级，然后把剩余部分变成子级
		// 然后在父级的indices中添加索引
		// 绝对路径添加完整的数据

		if i < len(t.Path) {
			child := &RadixNode{
				Path:     t.Path[i:],
				FullPath: t.FullPath,
				Indices:  t.Indices,
				End:      t.End,
				Children: t.Children,
				PassCnt:  t.PassCnt - 1,
				// PassCnt: func() int {
				// 	if t.Path[:i] != "" {
				// 		return t.PassCnt - 1
				// 	}
				// 	return t.PassCnt
				// }(),
			}

			t.Indices = string(t.Path[i])
			t.Children = []*RadixNode{child}
			t.FullPath = t.FullPath[:len(t.FullPath)-(len(t.Path)-i)]
			t.Path = t.Path[:i]
			t.End = false

		}

		// 如果公共前缀长度小于插入的word
		// 说明需要拆分当前的word，并且剩下的部分可能与当前节点的子节点还有重合
		// 循环当前节点的indices，然后找到所在的子节点,然后将当前节点设置为该找到的子节点
		// 循环进行
		if i < len(word) {
			word = word[i:]
			for idx, v := range t.Indices {
				if v == rune(word[0]) {
					t = t.Children[idx]
					continue LOOP
				}
			}

			t.Indices += string(word[0])
			child := &RadixNode{
				Path:     word,
				FullPath: fullWord,
				Indices:  "",
				End:      true,
				Children: []*RadixNode{},
				PassCnt:  1,
			}
			t.Children = append(t.Children, child)
			return
		}

		// 如果公共前缀等于插入的word
		// 那么直接将该节点的end设置为true
		// 结束

		t.End = true
		return
	}

}

func (t *RadixTree) Search(word string) bool {
	// return false
	node := t.Root.search(word)
	return node != nil && node.End && node.FullPath == word
}

func (t *RadixNode) search(word string) *RadixNode {
	move := t
LOOP:
	for {
		prefix := move.Path

		// 如果word的长度大于当前节点
		// 获取word的当前节点Path长度的前缀和当前节点进行比较
		// 如果两个前缀不相等，说明该word不存在
		// 如果两个前缀相等，那么获取word剩余的部分在当前节点的indices中进行查找到匹配的节点
		// 将当前节点替换为找到的节点，继续进行上一步(循环)
		if len(word) > len(prefix) {
			if word[:len(prefix)] != prefix {
				return nil
			}

			word = word[len(prefix):]

			for idx, v := range move.Indices {
				if rune(word[0]) == v {
					move = move.Children[idx]
					continue LOOP
				}
			}

			return nil
		}

		// 如果word 等于当前节点的path，那么精准匹配返回该节点
		if prefix == word {
			return move
		}

		return move
	}
}

func (t *RadixTree) Delete(word string) bool {
	// 如果找到了该节点不存在，不执行操作
	if !t.Search(word) {
		return false
	}

	// 从根节点开始，如果根节点的path
	return t.Root.delete(word)
}

func (t *RadixNode) delete(word string) bool {
	//如果当前节点path 和 word 相等

	//    如果当前节点没有子节点
	//    直接将当前节点置空

	//    如果当前节点只有一个子节点
	//    将当前节点的passCnt-1
	//    将当前节点的end 设置为false
	//    合并当前节点和子节点

	//    如果当前节点有多个节点
	//    将当前节点的end设置为false
	//    将当前节点的passCnt-1
	if len(word) == len(t.Path) {
		if len(t.Children) == 0 {
			t.Path = ""
			t.FullPath = ""
			t.End = false
			t.PassCnt--
			return true
		}
		if len(t.Children) == 1 {
			t.Path += t.Children[0].Path
			t.FullPath = t.Children[0].FullPath
			t.PassCnt -= 1
			t.End = false
			t.Children = t.Children[0:0]
			return true
		}

		t.End = false
		t.PassCnt--
		return true
	}

	//如果word长度大于当前节点的path
	//    说明word不存在，不处理
	if len(word) > len(t.Path) {
		return false
	}

	//如果word长度小于当前节点的path

	//    首先截取word[:path]长度的word，并将word设为截取的数据

	//    如果截取的word不等于path,那么结束
	//    如果截取的word等于path,说明当前节点的子节点可能存在
	//    遍历当前节点的indices 找当子节点，将指针设置为找到的子节点
	//    利用 continue GOTO 继续执行以上操作

	if len(word) < len(t.Path) {
	LOOP:
		for {
			word := word[:len(t.Path)]

			if word != t.Path {
				return false
			}

			if word == t.Path {
				c := word[0]
				for idx, v := range t.Indices {
					if rune(c) == v {
						t = t.Children[idx]
						continue LOOP
					}
				}

				t.End = false
				return true
			}

		}

	}

	return false
}

//PassCnt 获取通过该节点word的数量
func (t *RadixTree) PassCnt(prefix string) int {
	node := t.Root.search(prefix)
	if node == nil || !strings.HasPrefix(node.FullPath, prefix) {
		return 0
	}

	return node.PassCnt
}

//StartWith 检查前缀是否存在
func (t *RadixTree) StartWith(prefix string) bool {
	node := t.Root.search(prefix)
	return node != nil && strings.HasPrefix(node.FullPath, prefix)
}

//getCommonPrefixIdx 获取word1和word2的公共前缀
func getCommonPrefixIdx(word1 string, word2 string) int {
	i := 0
	for len(word1) > i && len(word2) > i && word1[i] == word2[i] {
		i++
	}

	return i
}
